package leetcode

import kotlinetc.println

//https://leetcode.com/problems/restore-ip-addresses/
/**
Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
长度大于 12 .无法分割
长度4只有一种分法
 */
fun main(args: Array<String>) {

    "25525511135".length.println()
    restoreIpAddresses("010010").toList()
            .println()
}

fun restoreIpAddresses(s: String): List<String> {


    val result = arrayListOf<String>()


    val len = s.length
    if (len !in 4..12) return result

    for (i in 1..3) {
        if (len - i !in 3..9) continue
        if (i > 1 && s[0] == '0') continue

        for (j in 1..3) {
            if (len - i - j !in 2..6) continue
            if (j == 3 && s[i] >= '3') continue
            if (j > 1 && s[i] == '0') continue

            for (k in 1..3) {
                val last = len - i - j - k
                if (last !in 1..3)
                    continue
                if (last ==3&&s[i+j+k]>='3')
                    continue
                if (last > 1 && s[i + j + k] == '0')
                    continue
                if (k == 3 && s[i + j] >= '3')
                    continue
                if (k > 1 && s[i + j] == '0')
                    continue


                val part1 = s.substring(0, i).toInt()
                val part2 = s.substring(i, i + j).toInt()
                val part3 = s.substring(i + j, i + j + k).toInt()
                val part4 = s.substring(i + j + k, len).toInt()

                println("$part1.$part2.$part3.$part4")

                if (part1.isValidIpPart() && part2.isValidIpPart() && part3.isValidIpPart() && part4.isValidIpPart()) {
                    println("$i $j $k $last")
                    result.add("$part1.$part2.$part3.$part4")
                }

            }
        }
    }

    return result
}


public fun Int.isValidIpPart() = this in 0..255